import heapq
import numpy

from .space import Position


class PriorityQueue(object):
    def __init__(self):
        self.__heap = []
        self.__dict = {}
    
    def add(self, priority, item):
        if item in self.__dict:
            self.__dict[item] += 1
        else:
            self.__dict[item]  = 1
        
        heapq.heappush(self.__heap, (priority, item))
    
    def pop(self):
        priority, item = heapq.heappop(self.__heap)
        
        if self.__dict[item] == 1:
            del self.__dict[item]
        else:
            self.__dict[item] -= 1
        
        return (priority, item)
    
    def __len__(self):
        return len(self.__heap)
    
    def __contains__(self, item):
        return item in self.__dict
    
    def __iter__(self):
        return iter(self.__heap)


class PathingMap(object):
    def __init__(self, width, height):
        self._width  = width
        self._height = height
        self._array  = numpy.zeros((width, height), numpy.bool_)
    
    @property
    def width(self):
        return self._width
    
    @property
    def height(self):
        return self._height
    
    def set_passable(self, position, is_passable):
        self._array[position.x, position.y] = is_passable
    
    def is_passable(self, position):
        if self.includes(position):
            return self._array[position.x, position.y]
        else:
            return False
    
    def includes(self, position):
        return (0 <= position.x < self.width and
                0 <= position.y < self.height)
    
    def find_path(self, position, target):
        def neighbours_of(position):
            for neighbour in position.neighbours:
                if not self.is_passable(neighbour):
                    if not self.includes(neighbour):
                        continue
                    
                    if neighbour not in target.area:
                        continue
                
                if (neighbour.x != position.x and
                    neighbour.y != position.y):
                    cost = 3
                else:
                    cost = 2
                    
                yield (cost, neighbour)
        
        def is_target(position):
            return position in target.area
        
        return find_path(position, neighbours_of, is_target)



def retrace_path(position, parents):
    path = [position]
    
    while path[-1] in parents:
        path.append(parents[path[-1]])
    
    return reversed(path)


def find_path(position, neighbours_of, is_target):
    open    = PriorityQueue()
    closed  = set()
    parents = {}
    costs   = {}
    
    open.add(0, position)
    
    while open:
        spent, position = open.pop()
        
        if is_target(position):
            return list(retrace_path(position, parents))
        
        closed.add(position)
        
        for cost, neighbour in neighbours_of(position):
            if neighbour in closed:
                continue
            
            total = spent + cost
            
            if neighbour in costs and total >= costs[neighbour]:
                continue
            
            costs  [neighbour] = total
            parents[neighbour] = position
            
            open.add(total, neighbour)
    
    return []
